package algorithm.leetcode.I201to400;

import java.util.Arrays;

public class Q300 {

    public int lengthOfLIS(int[] nums) {

        if (nums.length < 2) return nums.length;

        // dp数组的含义是以第i个数字结尾的最长上升子序列
        // 但是包含最后一个数字的子序列不一定是最长的
        // 所以需要一个全局最大值来记录
        int maxLength = 1;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);

        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j]+1);
            }
            maxLength = Math.max(maxLength, dp[i]);
        }

        return maxLength;
    }



    public static void main(String[] args) {
        Q300 tzz = new Q300();
        int[] arr = {10,9,2,5,3,7,101,18};
        System.out.println(tzz.lengthOfLIS(arr));
    }
}
